#define _CRT_SECURE_NO_WARNINGS
#include"Sort.h"
void ArrayPrint(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", *(a + i));
	}
	printf("\n");
}

void InsertSort(int* a, int n)
{
	for (int i = 1; i < n; i++)
	{
		int temp=a[i];
		int end=i-1;
		while (end >= 0)
		{
			if (temp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
				break;
		}
		a[end + 1] = temp;
	}
}

void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap /= 2;
		for (int i = gap; i < n; i+=gap)
		{
			int temp = a[i];
			int end = i - gap;
			while (end >= 0)
			{
				if (temp < a[end])
				{
					a[end + gap] = a[end];
					end-=gap;
				}
				else
					break;
			}
			a[end + gap] = temp;
		}

	}



}

void SelectSort(int* a, int n)
{
  

	int left = 0;
	int right = n - 1;

	while (left <=right)
	{
		int maxi = right, mini = left;
		for (int i = left; i < right; i++)
		{
			if (a[maxi] < a[i])
				maxi = i;
			if (a[mini] > a[i])
				mini = i;
		}
		swap(&a[left], &a[mini]);
		if (left == maxi)
		{
			maxi = mini;
		}
		swap(&a[right], &a[maxi]);


		right--;
		left++;

	}

}


void swap(int* a, int* b)
{
	int temp = *a;
	*a = *b;
	*b = temp;

}

void AdjustDwon(int* a, int n, int root)
{


	int parent = root;
	int child = root * 2 + 1;
	

	while (child < n)
	{
		if (child + 1 < n && a[child] < a[child + 1])
		{
			swap(&a[child], &a[child + 1]);
		}
	
		if (a[child] > a[parent])
		{
			swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;

		}
		else
			break;
	}

}


void HeapSort(int* a, int n)
{
	for (int i = (n - 1 - 1) / 2; i >=0; i--)
	{
		AdjustDwon(a, n, i);
	}
     
	int end = n;
	while (end > 0)
	{
		swap(&a[0], &a[end - 1]);
		AdjustDwon(a, end - 1, 0);
		end--;
	}
}

void BubbleSort(int* a, int n)
{
	int change = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 1; j < n - i; j++)
		{
			if (a[j - 1] > a[j])
			{
				change = 1;
				swap(&a[j - 1], &a[j]);
			}
		}
		if (change == 0)
			break;
	}


}

void _MergeSort(int* a, int left, int right, int* temp)
{  

	if (left == right)
		return;
	int mid = left + (right - left) / 2;

	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;

	_MergeSort(a, left, mid, temp);
	_MergeSort(a, mid + 1, right, temp);
	


	int i = left;
	while (begin1 <=end1 && begin2 <=end2)
	{
		if (a[begin1] <= a[begin2])
		{
			temp[i++] = a[begin1++];
		}
		else
		{
			temp[i++] = a[begin2++];
		}

	}

	while (begin1 <= end1)
	{
		temp[i++] = a[begin1++];
	}

	while (begin2 <= end2)
	{
		temp[i++] = a[begin2++];
	}

	memcpy(a + left, temp + left, sizeof(int) * (i - left));


}

void MergeSort(int* a, int n)
{
	int* temp = (int*)malloc(sizeof(int) * n);
	_MergeSort(a, 0, n - 1, temp);
	free(temp);
}



void MergeSortNonR(int* a, int n)
{
	
	int* temp = (int*)malloc(sizeof(int) * n);
	if (temp == NULL)
	{
		perror("malloc fail");
		return;
	}

	int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			int begin1 = i, end1 = begin1+ gap - 1,k=begin1;
			int begin2 = end1+1, end2 = begin2+gap-1;
			
			if (end1 >= n || begin2 >= n)
				break;
			if (end2 >= n)
				end2 = n - 1;

			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
					temp[k++] = a[begin1++];
				else
					temp[k++] = a[begin2++];

			}
			while (begin1 <= end1)
			{
				temp[k++] = a[begin1++];
			}
			while ( begin2 <= end2)
			{
					temp[k++] = a[begin2++];

			}
			memcpy(a+i , temp+i, sizeof(int) * (end2-i+1));

			

		}

		gap *= 2;

	}



	free(temp);



}



void CountSort(int* a, int n)
{

	int max, min;
	max = a[0];
	min = a[0];

	for (int i = 0; i < n; i++)
	{
		if (a[i] > max)
			max = a[i];
		if (a[i] < min)
			min = a[i];
	}
	int range = max - min + 1;
	int* CountA = (int*)malloc(sizeof(int) * range);
	if (CountA == NULL)
	{
		perror("malloc fail");
		return;
	}

	memset(CountA, 0, range*sizeof(int));

	for (int i = 0; i < n; i++)
	{
		(CountA[a[i] - min])++;
	}
	int k = 0;

	for (int i = 0; i < range; i++)
	{
		while (CountA[i]--)
		{
			a[k++] = min + i;
		}
	}


	free(CountA);

}

int PartSort1(int* a, int left, int right)
{
	if (left >= right)
		return;
     
	int keyi = left;

	int begin = left;
	int end = right;
	while (begin < end)
	{

		while (begin < end && a[end] >= a[keyi])
			end--;

		while (begin < end && a[begin] <= a[keyi])
			begin++;

		swap(&a[begin],&a[end]);
	}

	swap(&a[keyi], &a[end]);
	keyi = end;
	return keyi;

}

int PartSort2(int* a, int left, int right)
{

	if (left >= right)
		return;

	int begin = left;
	int end = right;

	int hole = left;
	int hole_n = a[left];
    
	while (begin < end)
	{
		while (begin < end && a[end] >= hole_n)
			end--;

		a[hole] = a[end];
		hole = end;

		while (begin < end && a[begin] <= hole_n)
			begin++;

		a[hole] = a[begin];
		hole = begin;

	}
	a[hole] = hole_n;
	return hole;

}


int PartSort3(int* a, int left, int right)
{
	if (left >= right)
		return;

	int begin = left;
	int end = right;

	int keyi = begin;
	int prev = left;
	int cur = left + 1;

	while (cur <= end)
	{
	    	
		if (a[cur] < a[keyi] && (++prev) != cur)
		{
			swap(&a[cur], &a[prev]);
		}

		cur++;
	}
	
	swap(&a[prev], &a[keyi]);
	return prev;



}



void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;
	int begin = left;
	int end = right;
	int keyi = PartSort3(a, begin, end);

	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);


}

void QuickSortNonR(int* a, int left, int right)
{
	St st;
	stack_init(&st);
	stack_push(&st, right);
	stack_push(&st, left);

	while (!is_empty(&st))
	{
		int begin= stack_pop(&st);
		int end = stack_pop(&st);
		int keyi = PartSort3(a, begin, end);

		if (keyi + 1 < end)
		{
			stack_push(&st, end);
			stack_push(&st, keyi+1);

		}
		if (keyi - 1 > begin)
		{
			stack_push(&st, keyi-1);
			stack_push(&st, begin);

		}

	}



}